package
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.KeyboardEvent;
	import flash.events.MouseEvent;
	import flash.events.TimerEvent;
	import flash.ui.Keyboard;
	import flash.utils.Timer;
	
	[SWF(width='500',height='500',backgroundColor='0xFFFFFF',frameRate='30')]
	
	public class PathFinding extends Sprite
	{
		private static var vert:Number = 0x008855;
		private static var bleu:Number = 0x005588;
		private static var rouge:Number = 0x880000;
		private static var noir:Number = 0x000000;
		private static var jaune:Number = 0xFFFF00;
		private static var orange:Number = 0xD2691E;
		private static var blanc:Number = 0xffffff;
		private static var gris:Number = 0x666666;
		
		private var _cote:int;
		private var _width:int;
		private var _nb_case:int;
		private var proba_obstacle:Number;
		
		private var _src:Node;
		private var _dest:Node;
		private var _current:Node;
		private var _ind:int;
		private var _path:Array;
		
		private var _srcEnnemy:Node;
		private var _destEnnemy:Node;
		private var _currentEnnemy:Node;
		private var _indEnnemy:int;
		private var _pathEnnemy:Array;
		
		private var _cmpt:int;
		private var _ennemy:int;
		
		private var _ctrlKey:Boolean;
		
		private var timer:Timer;
		private var timerEnnemy:Timer;
		
		public function PathFinding()
		{	
			_cote = 10;
			_width = stage.stageWidth / _cote;
			_nb_case = stage.stageWidth *  stage.stageHeight / (_cote * _cote);
			proba_obstacle = 20;
			_cmpt = 0;
			_ctrlKey = false;
			
			genGrid();	
			
			this.stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown);
			this.stage.addEventListener(KeyboardEvent.KEY_UP, onKeyUP);
		}
		
		private function genGrid():void
		{
			var x:int;
			var y:int;
			var rand:Number;
			for (var i:int = 0; i < _nb_case; i++)
			{
				x = case_x(i);
				y = (i/_width);
				
				rand = 100 * Math.random();
				
				var node:Node = new Node(10);
				node.x = x*_cote;
				node.y = y*_cote;
				
				if (rand > proba_obstacle)
				{
					drawRect(node, vert);
					node.name = "normal";
				}	
				else
				{
					drawRect(node, bleu);
					node.name = "obstacle";
				}
				
				node.addEventListener(MouseEvent.CLICK,onClick);
				
				this.addChild(node);
			}
		}
		
		private function reGenGrid():void
		{
			var x:int;
			var y:int;
			var rand:Number;
			for (var i:int = 0; i < _nb_case; i++)
			{
				var node:Node = getChildAt(i) as Node;
				
				rand = 100 * Math.random();
				
				if (rand > proba_obstacle)
				{
					drawRect(node, vert);
					node.name = "normal";
				}
				else
				{
					drawRect(node, bleu);
					node.name = "obstacle";
				}
			}
		}
		
		private function case_x(i:int):int
		{
			if (i % _width == 0)
				return 0;
			
			var x:int = i;
			
			while(x > _width)
				x -= _width;
			
			return x;
		}
		
		private function drawRect(o:Object, color:Number):void
		{
			o.graphics.beginFill(color, 1);
			o.graphics.lineStyle(1,0x000000);
			o.graphics.drawRect(0, 0, _cote, _cote);
			o.graphics.endFill();	
		}
		
		private function onClick(e:MouseEvent):void
		{
			var tmp:Node;
			tmp = e.target as Node;
			if (tmp.name != "obstacle")
			{
				
				if (!_ctrlKey)
				{
					
					switch(_cmpt)
					{
						case 0 :
							_src = tmp;
							drawRect(tmp, noir);
							_cmpt = 1;
							break;
				
						case 1 :
							_dest = tmp;
							drawRect(tmp, blanc);
							_cmpt = 2;
							break;
					}
				}
				
				else 
				{
					switch(_ennemy)
					{
						case 0 :
							_srcEnnemy = tmp;
							drawRect(tmp, rouge);
							_ennemy = 1;
							break;
				
						case 1 :
							_destEnnemy = tmp;
							drawRect(tmp, orange);
							_ennemy = 2;
							
							_pathEnnemy = findPath( _srcEnnemy, _destEnnemy, findConnectedNodes );
							//drawPath( _pathEnnemy, orange );
							
							timerEnnemy = new Timer(600, 0);
							timerEnnemy.addEventListener(TimerEvent.TIMER, onTimerEnnemy);
							timerEnnemy.start();
							
							_indEnnemy = 0;
							_currentEnnemy = _pathEnnemy[_indEnnemy];
							_currentEnnemy.name = "ennemy";
							drawRect(_currentEnnemy, rouge);
							break;
					}
				}
			}
		}
		
		
		private function onKeyDown(e:KeyboardEvent):void 
		{	
			switch (e.keyCode) 
			{	
				case Keyboard.SPACE: 
				{
					if (_cmpt >= 2)
					{
						_path = findPath( _src, _dest, findConnectedNodes );
						drawPath( _path, jaune );
						
						timer = new Timer(600, 0);
						timer.addEventListener(TimerEvent.TIMER, onTimer);
						timer.start();
						
						_ind = 0;
						_current = _path[_ind];
						drawRect(_current, gris);
					}
					break;
				}
				
				case Keyboard.CONTROL:
				{
					if (!_ctrlKey)
					{
					_ctrlKey = true;
					}
					break;
				}
				
				case 82: 
				{
					if(timer != null)
						timer.stop();
					if (timerEnnemy != null)
						timerEnnemy.stop();
					reGenGrid();
					_cmpt = 0;
					_ennemy = 0;
					break;
				}
					
				default:
			}
		}
		
		private function onKeyUP(e:KeyboardEvent):void 
		{	
			switch (e.keyCode) 
			{	
				case Keyboard.CONTROL:
				{
					_ctrlKey = false;
					break;
				}
					
				default:
			}
		}
		
		private function drawPath(nodes:Array, color:Number):void
		{
			if (!nodes) return;
			
			var n:Node;		
			
			for (var i:int = 0; i < nodes.length; ++i) {
				n = nodes[i];
				if (n != _src && n != _dest)
					n.highlight(color);
			}
		}
		
		private function getXIndex(node:Node):Number
		{
			return node.x / _cote;
		}
		
		private function getYIndex(node:Node):Number
		{
			return node.y / _cote;
		}
		
		public function findConnectedNodes( node:Node , diagonale:Boolean):Array
		{
			var n:Node = node;
			var connectedNodes:Array = [];			
			var testNode:Node;
			
			var _x:int = getXIndex(n);
			var _y:int = getYIndex(n);	
			var _case:int = _x+_y*_width;
			
			if (_x > 0)
			{
				testNode = this.getChildAt(_case - 1) as Node;
				if ( testNode.name != "obstacle")
					connectedNodes.push( testNode );
			}
			
			if (_x < _width-1)
			{
				testNode = this.getChildAt(_case + 1) as Node;
				if ( testNode.name != "obstacle")
					connectedNodes.push( testNode );
			}
				
			if (_y > 0)
			{
				testNode = this.getChildAt(_case - _width) as Node;
				if ( testNode.name != "obstacle")
					connectedNodes.push( testNode );
			}
				
			if (_y < _width-1)
			{
				testNode = this.getChildAt(_case + _width) as Node;
				if ( testNode.name != "obstacle")
					connectedNodes.push( testNode );
			}
			
			if (diagonale)
			{
				
				if (_x > 0 && _y > 0)
				{
					testNode = this.getChildAt(_case - _width - 1) as Node;
					if ( testNode.name != "obstacle")
						connectedNodes.push( testNode );
				}
				
				if (_x < _width-1 && _y > 0)
				{
					testNode = this.getChildAt(_case - _width + 1) as Node;
					if ( testNode.name != "obstacle")
						connectedNodes.push( testNode );
				}
				
				if (_x < _width-1 && _y < _width-1)
				{
					testNode = this.getChildAt(_case + _width + 1) as Node;
					if ( testNode.name != "obstacle")
						connectedNodes.push( testNode );
				}
				
				if (_x > 0 && _y < _width-1)
				{
					testNode = this.getChildAt(_case + _width + 1) as Node;
					if ( testNode.name != "obstacle")
						connectedNodes.push( testNode );
				}
			}
			
			return connectedNodes;
		}
		
		public function manhattanHeuristic(node:Node, destinationNode:Node, cost:Number = 1.0):Number
		{	
			return Math.abs(getXIndex(node) - getXIndex(destinationNode)) * cost + 
				Math.abs(getYIndex(node) - getYIndex(destinationNode)) * cost;
		}
		
		public function buildPath(destinationNode:Node, startNode:Node):Array {			
			var path:Array = [];
			var node:Node = destinationNode;
			path.push(node);
			while (node != startNode) {
				node = node.parentNode;
				path.unshift( node );
			}
			
			return path;			
		}
		
		public function isOpen(node:Node, openNodes:Array):Boolean {
			
			var l:int = openNodes.length;
			for (var i:int = 0; i < l; ++i) {
				if ( openNodes[i] == node ) return true;
			}
			
			return false;			
		}
		
		public function isClosed(node:Node, closedNodes:Array):Boolean {
			
			var l:int = closedNodes.length;
			for (var i:int = 0; i < l; ++i) {
				if (closedNodes[i] == node ) return true;
			}
			
			return false;
		}
		
		public function findPath(firstNode:Node, destinationNode:Node, connectedNodeFunction:Function ):Array 	
		{	
			var openNodes:Array = [];
			var closedNodes:Array = [];			
			
			var currentNode:Node = firstNode;
			var testNode:Node;
			
			var l:int;
			var i:int;
			
			var connectedNodes:Array;
			var travelCost:Number = 1.0;
			
			var g:Number;
			var h:Number;
			var f:Number;
			
			currentNode.g = 0;
			currentNode.h = manhattanHeuristic(currentNode, destinationNode, travelCost);
			
			currentNode.f = currentNode.g + currentNode.h;
			
			while (currentNode != destinationNode) {
				
				connectedNodes = connectedNodeFunction( currentNode , false);	
				
				l = connectedNodes.length;
				
				//trace(l.toString());
				
				for (i = 0; i < l; ++i) {
					
					testNode = connectedNodes[i];
					
					if (testNode == currentNode) continue;					
					
					//For our example we will test just highlight all the tested nodes
					//if (testNode != _src && testNode != _dest)
					//	testNode.highlight(gris);
					
					//g = currentNode.g + Pathfinder.heuristic( currentNode, testNode, travelCost); //This is what we had to use here at Untold for our situation.
					//If you have a world where diagonal movements cost more than regular movements then you would need to determine if a movement is diagonal and then adjust
					//the value of travel cost accordingly here.
					g = currentNode.g + travelCost;
					h = manhattanHeuristic( testNode, destinationNode, travelCost);
					f = g + h;
					
					if ( isOpen(testNode, openNodes) || isClosed( testNode, closedNodes) )
					{
						if(testNode.f > f)
						{
							testNode.f = f;
							testNode.g = g;
							testNode.h = h;
							testNode.parentNode = currentNode;
						}
					}
					else {
						testNode.f = f;
						testNode.g = g;
						testNode.h = h;
						testNode.parentNode = currentNode;
						openNodes.push(testNode);
					}
					
				}
				closedNodes.push( currentNode );
				
				if (openNodes.length == 0) {
					return null;
				}
				openNodes.sortOn('f', Array.NUMERIC);
				currentNode = openNodes.shift() as Node;
			}
			
			return buildPath(destinationNode, firstNode);
		}
		
		private function findEnnemy(n:Node):Boolean
		{
			var connectedNodes:Array;
			connectedNodes = findConnectedNodes( n , true);
			trace(connectedNodes.length);
			for (var i:int = 0; i < connectedNodes.length; i++)
				if (connectedNodes[i].name == "ennemy")
					return true;
					
			return false;
		}
		
		private function onTimer(e:TimerEvent):void 
		{
			if (_ind == _path.length - 1)
			{
				drawRect(_current, vert);
				timer.stop();
				_cmpt = 0;
				
				for (var j:int = 0; j < _path.length; j++)
				{
					drawRect(_path[j], vert);
					_path[j] = null;
				}
			}
			
			else
			{
				if (!findEnnemy(_current))
				{
					_ind++;
					drawRect(_current, vert);
					
					for (var i:int = 0; i < _path.length; i++)
						if (_current == _path[i])
							drawRect(_current, jaune);
							
							if (_current == _src)
						drawRect(_current, noir);
							
					_current = _path[_ind];
					drawRect(_current, gris);
				}
			}
		}
		
		private function onTimerEnnemy(e:TimerEvent):void 
		{
			if (_indEnnemy == _pathEnnemy.length - 1)
			{
				_currentEnnemy.name = "";
				drawRect(_currentEnnemy, vert);
				timerEnnemy.stop();
				
				var tmp1:Node = _srcEnnemy;
				var tmp2:Node = _destEnnemy;
				_srcEnnemy = tmp2;
				_destEnnemy = tmp1;
				
				_pathEnnemy = findPath( _srcEnnemy, _destEnnemy, findConnectedNodes );
				//drawPath( _pathEnnemy, orange );
							
				timerEnnemy = new Timer(600, 0);
				timerEnnemy.addEventListener(TimerEvent.TIMER, onTimerEnnemy);
				timerEnnemy.start();
							
				_indEnnemy = 0;
				_currentEnnemy = _pathEnnemy[_indEnnemy];
				_currentEnnemy.name = "ennemy";
				drawRect(_currentEnnemy, rouge);
			}
			
			else
			{		
				_indEnnemy++;
				_currentEnnemy.name = "";
				drawRect(_currentEnnemy, vert);
				
				for (var i:int = 0; i < _path.length; i++)
					if (_currentEnnemy == _path[i])
						drawRect(_currentEnnemy, jaune);
				
				if (_currentEnnemy == _srcEnnemy || _currentEnnemy == _destEnnemy)
					drawRect(_currentEnnemy, orange);
					
				_currentEnnemy = _pathEnnemy[_indEnnemy];
				_currentEnnemy.name = "ennemy";
				drawRect(_currentEnnemy, rouge);
			}
		}
		
		
		
	}
}